#include <stdio.h>
#include <stdlib.h>

#define MAXN 30

typedef int ElementType;
typedef int Positions;
typedef struct QNode *PtrToQNode;
typedef PtrToQNode Queue;
typedef struct TNode *Position;
typedef Position BinTree;

//枚举类型
typedef enum
{
    true,
    false
} bool; 
//队列节点的定义
struct QNode
{
    Position *Data;//存储元素的数组
    Positions Front, Rear;//队列的头尾指针
    int MaxSize;//队列的最大容量
};

//树节点的定义
struct TNode
{
    ElementType Data;//节点数据
    BinTree Left;//指向左子树
    BinTree Right;//指向右子树
};

BinTree BuildTree(int Inorder[], int Postorder[], int N);
// void PreorderTraversal(BinTree T);
void LevelOrderTraversal(BinTree BT);//层序遍历数组
Queue CreatQueue();//创建队列
bool IsEmpty(Queue Q);//判断队列是否为空
void AddQ(Queue PtrQ, BinTree item);//添加元素到队列中
BinTree DeleteQ(Queue PtrQ);//出队

int main()
{
    BinTree T;
    int Inorder[MAXN], Postorder[MAXN], N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)//加入后序数组
        scanf("%d", &Postorder[i]);
    for (int j = 0; j < N; j++)//加入中序数组
        scanf("%d", &Inorder[j]);
    T = BuildTree(Inorder, Postorder, N);//构建二叉树
    // PreorderTraversal(T);
    LevelOrderTraversal(T);//层序输出
    return 0;
}


// 1.循环队列入队
void AddQ(Queue PtrQ, BinTree item)
{
    if (((int)(PtrQ->Rear + 1)) % (2 * MAXN) == PtrQ->Front)//判断循环队列是否满
    {
        printf("队列满");
        return;
    }
    PtrQ->Rear = (PtrQ->Rear + 1) % (2 * MAXN);
    PtrQ->Data[(int)(PtrQ->Rear)] = item;
}
bool IsEmpty(Queue Q)//判断队列是否为空
{
    return (Q->Front == Q->Rear);
}
// 2.出队
BinTree DeleteQ(Queue PtrQ)
{
    if (PtrQ->Front == PtrQ->Rear)
    {
        printf("队列空");
        return NULL;
    }
    else
    {
        PtrQ->Front = (PtrQ->Front + 1) %( 2 * MAXN);
        return PtrQ->Data[PtrQ->Front];
    }
}

Queue CreatQueue()//创建队列
{

    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (BinTree *)malloc(2 * MAXN * sizeof(ElementType));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = 2 * MAXN;
    return Q;
}
BinTree BuildTree(int Inorder[], int Postorder[], int N)//通过后序输出和中序输出构建树
{
    BinTree T;
    int p;

    if (!N)//树为空，递归终止
        return NULL;
    T = (BinTree)malloc(sizeof(struct TNode));
    T->Data = Postorder[N - 1];//根节点是后序最后一个
    T->Left = T->Right = NULL;
    for (p = 0; p < N; p++)
    {
        if (Inorder[p] == Postorder[N - 1])
            break;
    }
    T->Left = BuildTree(Inorder, Postorder, p);
    T->Right = BuildTree(Inorder + p + 1, Postorder + p, N - p - 1);
    return T;
}
/*void PreorderTraversal(BinTree T)
{
    if(T)
    {
        printf("%d",T->Data);
        PreorderTraversal(T->Left);
        PreorderTraversal(T->Right);
    }
}*/
void LevelOrderTraversal(BinTree BT)//层序输出
{
    Queue Q;
    BinTree T;
    if (!BT)//若是空树直接返回
        return;
    Q = CreatQueue();//创建空队列
    AddQ(Q, BT);

    //格式化输出实现方法
    T = DeleteQ(Q);
    printf("%d", T->Data);
    if (T->Left)
        AddQ(Q, T->Left);
    if (T->Right)
        AddQ(Q, T->Right);
    while (!IsEmpty(Q))
    {
        
        T = DeleteQ(Q);
        printf(" %d", T->Data);//访问队列结点
        if (T->Left)
            AddQ(Q, T->Left);
        if (T->Right)
            AddQ(Q, T->Right);
    }
    
}
